#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <limits>

using std::cout, std::cin;

using int64 = int64_t;
const int64 max_nm = 5e3+5;
int64 n, m, a[max_nm], b[max_nm], hist, dp[max_nm], costs[max_nm][max_nm], inf=std::numeric_limits<int64>::max();

auto mpow(int64 b, int64 e)->int64{
    if(b==1)return 1;
    int64 ret{b};
    for(int64 i{2};i<=e;i++){
        ret*=b;
    }
    return ret;
}

int main(){
    cin>>n>>m;
    std::fill(dp, dp+1+n, inf);
    dp[0]=0;
    for(int64 i{1};i<=m;i++){
        cin>>a[i]>>b[i];
        costs[i][1] = a[i];
        for(int64 j{2};j<=n;j++){
            costs[i][j] = a[i]*mpow(j, b[i]);
            // cout<<costs[i][j]<<' ';
        }
        // cout<<'\n';
        for(int64 j{n};j>=1;j--){
            for(int64 x{1};x<=j;x++){
                if(dp[j-x]!=inf){
                    dp[j]=std::min(
                        dp[j],
                        dp[j-x]+costs[i][x]
                    );
                }
            }
        }
    }
    cout<<dp[n]<<'\n';
}